class Solution {
public:
    int minSteps(int n) {
        if(n == 1) return 0;
        if(n == 2) return 2;
        
        vector<int> dp(n+1);
        dp[2] = 2;
        for(int i = 3;i <= n;i++){
            dp[i] = i;
            for(int j = 2;j <= pow(i,0.5);j++){
                if(i % j == 0){
                    dp[i] = min(dp[i],dp[i/j]+dp[j]);
                }
            }
        }
        return dp[n];
    }
};
